package LeetCodeHot100TopInterview;

public class Q198_RobHouse {
    //打家劫舍
    //相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
    //给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额

    //经典从左到右尝试问题 转 dp
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        return process(nums, 0, false);
    }
    //lastRobed ==> 上一家是否盗窃过
    public int process(int[] nums, int index, boolean lastRobed){

        if (index == nums.length - 1){
            return lastRobed ? 0 : nums[index];
        }

        //上一个位置盗窃过 到下一个位置做决策
        if (lastRobed){
            return process(nums, index + 1, false);
        }
        //决策 当前位置偷与不偷
        //yes
        int yes = process(nums, index + 1, true) + nums[index];
        //no
        int no = process(nums, index + 1, false);

        return Math.max(yes, no);
    }

    //解决超时问题
    public int rob_DP(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        if (nums.length == 1){
            return nums[0];
        }

        int[] dp = new int[nums.length];
        int L = nums.length - 1;
        //倒数第一个位置 只有一个 为何不要
        dp[L] = nums[L];
        //倒数第二个位置 自己要最后一个不要 或者自己不要最后一个要 比大小
        dp[L - 1] = Math.max(nums[L - 1], nums[L]);
        for (int i = L - 2; i > -1; i--) {
            //要或者不要
            dp[i] = Math.max(nums[i] + dp[i + 2], dp[i + 1]);
        }
        return dp[0];
    }

    public static void main(String[] args) {
        Q198_RobHouse fun = new Q198_RobHouse();
        System.out.println(fun.rob_DP(new int[]{2}));
    }
}
